package cn.zifangsky.array.questions;

import org.junit.Test;

/**
 * 搜索旋转排序数组
 *
 * <p>给你一个升序排列的整数数组 nums ，和一个整数 target 。</p>
 * <p>假设按照升序排序的数组在预先未知的某个点上进行了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。</p>
 * <p>请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。</p>
 *
 * <ol>
 *     <li>输入：[nums = [4, 5, 6, 7, 0, 1, 2], target = 0；结果：4</li>
 *     <li>输入：nums = [4, 5, 6, 7, 0, 1, 2], target = 3；结果：-1</li>
 *     <li>输入：nums = [1], target = 0；结果：-1</li>
 * </ol>
 *
 * @author zifangsky
 * @date 2020/10/21
 * @since 1.0.0
 */
public class Problem_007_SearchTargetValueInARotatedSortedArray {

    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        int[] arr1 = new int[]{4, 5, 6, 7, 0, 1, 2};
        int[] arr2 = new int[]{3, 4, 5, 1, 2};
        int[] arr3 = new int[]{1};

        //结果：4
        System.out.println("方法一：" + this.search1(arr1, 0) + "，方法二：" + this.search2(arr1, 0));
        //结果：-1
        System.out.println("方法一：" + this.search1(arr1, 3) + "，方法二：" + this.search2(arr1, 3));
        //结果：0
        System.out.println("方法一：" + this.search1(arr2, 3) + "，方法二：" + this.search2(arr2, 3));
        //结果：4
        System.out.println("方法一：" + this.search1(arr2, 2) + "，方法二：" + this.search2(arr2, 2));
        //结果：0
        System.out.println("方法一：" + this.search1(arr3, 1) + "，方法二：" + this.search2(arr3, 1));
        //结果：-1
        System.out.println("方法一：" + this.search1(arr3, 0) + "，方法二：" + this.search2(arr3, 0));
    }

    /**
     * 方法一（暴力破解）：直接单次循环遍历搜索整个数组找到目标索引，时间复杂度为 O(n)。
     */
    private int search1(int[] nums, int target) {
        if(nums == null || nums.length < 1){
            throw new IllegalArgumentException("参数存在异常！");
        }

        for(int i = 0; i < nums.length; i++){
            if(nums[i] == target){
                return i;
            }
        }

        return -1;
    }

    /**
     * 方法二（改进的二分查找，时间复杂度为O(log(n))）：
     * <ol>
     *     <li>基本思路参考题目 {@link Problem_006_FindTheSmallestValueInARotatedSortedArray#findMin2(int[] nums)}</li>
     *     <li>将数组一分为二后，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。</li>
     *     <li>此时有序部分用二分法查找，无序部分再一分为二循环这两个步骤。</li>
     * </ol>
     */
    private int search2(int[] nums, int target) {
        if(nums == null || nums.length < 1){
            throw new IllegalArgumentException("参数存在异常！");
        }

        int left = 0, right = nums.length - 1;
        while (left <= right){
            int mid = (right + left) / 2;
            //1. 如果 nums[mid]/nums[left]/nums[right] 恰好跟 target 相等，则直接返回
            if(nums[mid] == target){
                return mid;
            }
            if(nums[left] == target){
                return left;
            }
            if(nums[right] == target){
                return right;
            }

            //2. 如果 nums[left, mid] 是有序数组
            if(nums[left] <= nums[mid]){
                //2.1 如果 target 恰好在这一段有序数组中，则直接使用二分法查找
                if(nums[left] <= target && target <= nums[mid]){
                    return this.binarySearch(nums, left, mid, target);
                }
                //2.2 否则 target 在 nums(mid, right]，继续循环执行整个流程判断
                else{
                    left = mid + 1;
                }
            }
            //3. 如果 nums[mid, right] 是有序数组
            else{
                //3.1 如果 target 恰好在这一段有序数组中，则直接使用二分法查找
                if(nums[mid] <= target && target <= nums[right]){
                    return this.binarySearch(nums, mid, right, target);
                }
                //3.2 否则 target 在 nums[left, mid)，继续循环执行整个流程判断
                else{
                    right = mid -1;
                }
            }
        }

        return -1;
    }

    /**
     * 二分查找一个有序数组
     */
    private int binarySearch(int[] nums, int left, int right, int target) {
        if(nums == null || nums.length < 1){
            throw new IllegalArgumentException("参数存在异常！");
        }

        while (left <= right){
            int mid = (right + left) / 2;

            if(nums[mid] == target){
                return mid;
            }

            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

        return -1;
    }

}
